package com.bascker.algorithm.practice.dp;

/**
 * 比特位计数:
 *   给定一个 非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 *
 * For exmaple:
 *   in: 2      out: [0,1,1]
 *   in: 5      out: [0,1,1,2,1,2]
 *
 * @author bascker
 * @apiNote leetcode T338
 * @implNote https://gitee.com/bascker/algorithm/wikis/2%E3%80%81%E6%AF%94%E7%89%B9%E4%BD%8D%E8%AE%A1%E6%95%B0?sort_id=2982202
 */
public class CountBits {

    public int[] countBits(int num) {
        if (num == 0) {
            return new int[]{0};
        }
        int[] dp = new int[num + 1];
        dp[0] = 0;
        dp[1] = 1;
        int p = 1;
        for (int i = 2; i <= num; ++i) {
            if (p << 1 == i) {
                p = i;
                dp[i] = 1;
                continue;
            }

            // 状态转移方程
            dp[i] = dp[p] + dp[i - p];
        }

        return dp;
    }

}
